package com.wangbo.sort;

public class HeapSort {

    public static void heapSort(int[] arr) {
        int tail = arr.length - 1; // 遍历指针 tail, 从数组末尾左移到数组头
        if (tail > 0) {
            // 从右向左建堆，时间复杂度更低 O(N)
            // 把数组转换成大根堆
            // 遍历指针 i 从数组末尾左移到数组头
            for (int i = tail; i >= 0; i--) {
                heapify(arr, i, tail);
            }

            // 根节点和tail指向元素交换位置，tail指针左移
            swap(arr, 0, tail--);
            while (tail > 0) {
                heapify(arr, 0, tail); // 从新的根节点向下进行堆调整
                swap(arr, 0, tail--);
            }
        }
    }

    /**
     * 堆调整(向下)
     * index节点和左右孩子中的较大方比较大小，index节点较小则交换位置，继续向下比较，直到index节点大于等于或者没有孩子
     */
    public static void heapify(int[] arr, int index, int tail) {
        int left = index * 2 + 1; // 遍历指针，left: index的左孩子下标
        while (left <= tail) {
            int right = left + 1;
            int bigger = (right) <= tail && arr[right] > arr[left] ? right : left; // 左右子节点的较大方
            bigger = arr[bigger] > arr[index] ? bigger : index; // index和左右子节点中的较大方
            if (bigger == index) {
                break;
            } else {
                swap(arr, bigger, index);
                index = bigger;
                left = index * 2 + 1;
            }
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
